ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД «УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ» Інженерно-технічний факультет Кафедра копм’ютерних систем та мереж Розрахунково-графічна робота з дисципліни «Теоретичні основи цифрової обробки сигналів» на тему: «Розрахунок параметрів виконання алгоритму ШПФ»  студент IV-го курсу КСМ, ІТФ Бобуський Перевірив: Ваврук Є. Я. Ужгород-2012 Завдання Варіант № 3. Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними: Кількість точок 4096  Основа ШПФ 4  Прорідження часове  Частота роботи процесора 2,8 МГц  Розрядність вхідних даних 12  Тип вхідного інтерфейсу SPORT  Тип вихідного інтерфейсу PCI   Анотація В даній розрахунково-графічній роботі розглянуто спосіб реалізації алгоритму ШПФ за основою 4 з часовим прорідженням, описано механізми обчислення швидкого перетворення Фур`є з прорідженням в часі, аналіз блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора. В роботі також обчислено часові ресурси для виконання обчислення, створена функціональна схема системи та написана програма виконання заданої функції. Зміст Вступ 5 1 Теоретичний розділ 6 1.1 Опис швидкого перетворення Фур’є з прорідженням в часі 6 1.2 Приклад виконання для 1024-точкового перетворення за основою 4 12 2 Аналіз (розробка) блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора 15 3 Розрахунковий розділ 17 4 Розробка функціональної схем 18 5 Розробка програми виконання заданої функції 20 Висновки 24 Література 25 Вступ Перетворення Фур'є - це функція, що описує амплітуду та фазу кожної синусоїда, що відповідає певній частоті. Амплітуда представляє висоту кривої, а фаза - початкову точку синусоїда. Ці перетворення зворотні, при чому зворотнє перетворення має практично таку ж саму форму, що й пряме перетворення. Швидке перетворення Фур'є застосовується в багатьох галузях: радіолокации, стисненні відео та зображень, геології. Багато з цих задач вимагають виконання перетворень в реальному часі, з мінімальною часовою затримкою обчислень. Для зменшення часу, необхідного для виконання перетворень, можливо розпаралелювання задачі, виконання її на паралельній обчислювальній системі. Крім того, ці перетворення корисні при проектуванні фільтрів. Частотна характеристика фільтра може бути отримана за допомогою перетворення Фур’є його імпульсної реакції. І навпаки, якщо визначена частотна характеристика сигналу, то необхідна імпульсна реакція може бути отримана за допомогою зворотнього перетворення Фур’є над його частотною характеристикою. Цифрові фільтри можуть бути створені на основі їхньої імпульсної реакції, оскільки коефіцієнти фільтра з кінцевою імпульсною характеристикою (КІХ) ідентичні дискретній імпульсній реакції фільтра. 1 Теоретичний розділ 1.1 Опис швидкого перетворення Фур’є з прорідженням в часі Дискретний матеріальний сигнал у вигляді кінцевої часової послідовності x(nТ) запишемо як x(nТ), де
- число відліків, N – число відліків, T - період дискретизації. N - точкове дискретне перетворення Фур'є (ДПФ) задається формулою:
де X(k) - частотний k-ий відлік чи k-а спектральна складова сигналу (визначає вихідну частотну послідовність, спектр сигналу),
комплексна експонента, W- ядро перетворення. При зміні значення n*k на величину кратну N ядро
не змінюється (у силу періодичності синуса і косинуса). Тобто ядро по верхньому індексу є періодичною функцією з періодом N. Тому замість добутку n*k можна вставити залишок від ділення його на N , тобто (n*k) mod N. Cпектральна функція X(k) також має період N по аргументу k. Число множень дійсних відліків сигналу на комплексне ядро в (1) дорівнює N2, а число додавань комплексних чисел - (N -1)N. Кількість цих операцій різко зростає із збільшенням N і приводить до занадто великого часу перетворення. ДПФ стало широко застосовуватися після винаходу швидких алгоритмів, в основі яких лежить принцип зведення багатоточкового перетворення...